@InProceedings{CoutoSouzReze:2007:ExEfAl,
               author = "Couto, Marcelo C. and Souza, Cid C. de and Rezende, Pedro J. de",
          affiliation = "Institute of Computing, State University of Campinas, Campinas - 
                         Brazil and Institute of Computing, State University of Campinas, 
                         Campinas - Brazil and Institute of Computing, State University of 
                         Campinas, Campinas - Brazil",
                title = "An Exact and Efficient Algorithm for the Orthogonal Art Gallery 
                         Problem",
            booktitle = "Proceedings...",
                 year = "2007",
               editor = "Falc{\~a}o, Alexandre Xavier and Lopes, H{\'e}lio C{\^o}rtes 
                         Vieira",
         organization = "Brazilian Symposium on Computer Graphics and Image Processing, 20. 
                         (SIBGRAPI)",
            publisher = "IEEE Computer Society",
              address = "Los Alamitos",
             keywords = "Art Gallery, Exact Solution, Orthogonal Polygons, Integer 
                         Programming, Set Covering.",
             abstract = "In this paper, we propose an exact algorithm to solve the 
                         Orthogonal Art Gallery problem in which guards can only be placed 
                         on the vertices of the polygon \$ P\$ representing the gallery. 
                         Our approach is based on a discretization of \$ P\$ into a 
                         finite set of points in its interior. The algorithm repeatedly 
                         solves an instance of the Set Cover problem obtaining a minimum 
                         set \$ Z\$ of vertices of \$ P\$ that can view all points in 
                         the current discretization. Whenever \$ P\$ is completely 
                         visible from \$ Z\$ , the algorithm halts; otherwise, the 
                         discretization is refined and another iteration takes place. We 
                         establish that the algorithm always converges to an optimal 
                         solution by presenting a worst case analysis of the number of 
                         iterations that could be effected. Even though these could 
                         theoretically reach \$ O(n^4)\$ , our computational experiments 
                         reveal that, in practice, they are linear in \$ n\$ and, for \$ 
                         n\leq 200\$ , they actually remain less than three in almost all 
                         instances. Furthermore, the low number of points in the initial 
                         discretization, \$ O(n^2)\$ , compared to the possible \$ 
                         O(n^4)\$ atomic visibility polygons, renders much shorter total 
                         execution times. Optimal solutions found for different classes of 
                         instances of polygons with up to 200 vertices are also 
                         described.",
  conference-location = "Belo Horizonte, MG, Brazil",
      conference-year = "7-10 Oct. 2007",
                  doi = "10.1109/SIBGRAPI.2007.15",
                  url = "http://dx.doi.org/10.1109/SIBGRAPI.2007.15",
             language = "en",
                  ibi = "6qtX3pFwXQZG2LgkFdY/QGG9a",
                  url = "http://urlib.net/ibi/6qtX3pFwXQZG2LgkFdY/QGG9a",
           targetfile = "couto-ArtGallery.pdf",
        urlaccessdate = "2024, Apr. 29"
}